package com.wrial.middle;
/*
 * @Author  Wrial
 * @Date Created in 11:23 2020/8/2
 * @Description
 */

import java.util.Arrays;

public class LeetCode_300_最长上升子序列 {

    /**
     * 1.暴力解法，从第一个元素开始向后遍历，没遇到一个比当前大的就更新max，并记录子序列长度
     * 2.dp，dp[i]=Max(dp[j])+1  0<=j<i && nums[i]>nums[j]
     *
     * @param nums
     * @return
     */
    public int lengthOfLIS(int[] nums) {
        if(nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);//最小是1
        int ans = 1;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }


}
